package com.wang.violentrecursion;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @Author: along
 * @Create: 2021/4/26
 * @Description:打印一个字符串的所有子序列
 */
public class Demo03_PrintAllSubSequence {

        public static List<String> subs(String s) {
            char[] str = s.toCharArray();
            String path = "";
            List<String> ans = new ArrayList<>();
            process1(str, 0, ans, path);
            return ans;
        }
        //str固定 传入的字符串
        //index 此时来到的位置 该位置的字符 要 or 不要
        //如果index来到str的终止位置，把沿途路径所形成的答案放入ans中
        //之前做出的选择就是path
        //使用一个数组来存储ans，得到的结果可能有重复，比如一个字符串中存在相同的字符，可能会打印相同的子序列
        public static void process1(char[] str, int index, List<String> ans, String path) {
            if (index == str.length) {
                ans.add(path);
                return;
            }
            //不要该路径
            String no = path;
            process1(str, index + 1, ans, no);
            //要该路径
            String yes = path + String.valueOf(str[index]);
            process1(str, index + 1, ans, yes);
        }

        public static List<String> subsNoRepeat(String s) {
            char[] str = s.toCharArray();
            String path = "";
            HashSet<String> set = new HashSet<>();
            process2(str, 0, set, path);
            List<String> ans = new ArrayList<>();
            for (String cur : set) {
                ans.add(cur);
            }
            return ans;
        }
        //用set来存储得到的结果，即使字符串中存在相同的的字符，得到的子序列也会去重
        public static void process2(char[] str, int index, HashSet<String> set, String path) {
            if (index == str.length) {
                set.add(path);
                return;
            }
            String no = path;
            process2(str, index + 1, set, no);
            String yes = path + String.valueOf(str[index]);
            process2(str, index + 1, set, yes);
        }

        public static void main(String[] args) {
            String test = "aabc";
            List<String> ans1 = subs(test);
            List<String> ans2 = subsNoRepeat(test);

            for (String str : ans1) {
                System.out.println(str);
            }
            System.out.println("=================");
            for (String str : ans2) {
                System.out.println(str);
            }
            System.out.println("=================");

        }

}
